Given a convex set 𝒦\mathcal{K}, separation oracle S𝒦S_\mathcal{K} returns:

S𝒦={∅if 𝐲∈𝒦 separating hyperplane ℋif 𝐲∉𝒦 S_\mathcal{K}=\begin{cases} \emptyset & \textrm{if }\mathbf{y}\in \mathcal{K}\ \textrm{separating hyperplane } \mathcal{H} & \textrm{if }\mathbf{y}\notin \mathcal{K} \end{cases}

Let ℋ={𝐱:𝐚⊺𝐱=c}\mathcal{H} = \{\mathbf{x} : \mathbf{a}^\intercal \mathbf{x} = c\}.

used in ellipsoid method

References:

  1. https://www.chrismusco.com/amlds2023/notes/lecture09.html
  2. https://en.wikipedia.org/wiki/Hyperplane_separation_theorem